#ifndef MAP_H
#define MAP_H

#include <jimix/Globals.h>

#define MAP_HASH(x) ((u32int)x%S)

/**
  Implements a hashtable with chained hashing. The key must be able to be
  casted to a pointer and to an unsigned 32 bit integer.
**/
template <class K, class T, u32int S>
class Map
{
public:
  typedef bool (*EqualityPredicate)(K,K);
  typedef u32int (*HashFunction)(K,u32int);
  
  static bool genericEqPredicate(K a, K b)
  {
    return a == b;
  }
  static bool stringEqPredicate(K a, K b)
  {
    return (strcmp(a, b) == 0);
  }
  static u32int genericHashFunction(K x, u32int s)
  {
    return (u32int)x%s;
  }
  static u32int stringHashFunction(K x, u32int s)
  {
    u32int acc = 0;
    char *iterator = x;
    while (*iterator)
    {
      acc += (u32int)*iterator++;
    }
    return acc%s;
  }
  
  /**
    Generic constructor
  **/
  Map(EqualityPredicate eq=&genericEqPredicate,
      HashFunction h=&genericHashFunction) :
    nEntries(0), predicate(eq), hash(h)
  {
    for (int i = 0; i < S; i++)
    {
      array[i] = NULL;
    }
  }
  

  ~Map()
  {
  }
  

  /**
    Adds an item into the map
  **/
  void add(K key, T value)
  {
    // Find the correct bucket.
    array[hash(key,S)] = new Node(key, value, array[hash(key,S)]);
    nEntries++;
  }
  
  /**
    Removes an item from the map
  **/
  T remove(K key)
  {
    Node *bucket = array[hash(key,S)];
    Node *prev;
    if (!bucket)
    {
      return (T)0;
    }
    else
    {
      if (predicate(bucket->key, key))
      {
        array[hash(key,S)] = bucket->next;
        nEntries--;
        T tmp = bucket->value;
        delete bucket;
        return tmp;
      }
      else
      {
        prev = bucket;
        bucket = bucket->next;
        while (bucket)
        {
          if (predicate(bucket->key, key))
          {
            prev->next = bucket->next;
            T tmp = bucket->value;
            delete bucket;
            nEntries--;
            return tmp;
          }
          prev = bucket;
          bucket = bucket->next;
        }
      }
    }
    return (T)0;
  }
  
  /**
    Finds an item in the map.
  **/
  T lookup(K key)
  {
    Node *bucket = array[hash(key,S)];
    while(bucket)
    {
      if (predicate(bucket->key, key))
      {
        return bucket->value;
      }
      bucket = bucket->next;
    }
    return (T)0;
  }

  /**
    Returns the key of the n'th index in the map.
  **/
  K getKeyByIndex(u32int n)
  {
    s32int i = 0;
    u32int j = 0;
    Node *bucket = array[j];
    while(j < S)
    {
      if (bucket == NULL)
      {
        bucket = array[++j];
      }
      else
      {
        if (i == n)
        {
          break;
        }
        i++;
        bucket = bucket->next;
      }
    }
    if (i == n)
    {
      return bucket->key;
    }
    else
    {
      return (K)NULL;
    }
  }
  
  /**
     Returns the n'th index in the map.
  **/
  T getByIndex(u32int n)
  {
    if (n >= nEntries)
    {
      return (T)NULL;  
    }
    s32int i = 0;
    u32int j = 0;
    Node *bucket = array[j];
    while(j < S)
    {
      if (bucket == NULL)
      {
        bucket = array[++j];
      }
      else
      {
        if (i == n)
        {
          break;
        }
        i++;
        bucket = bucket->next;
      }
    }
    if (i == n)
    {
      return bucket->value;
    }
    else
    {
      return (T)NULL;
    }
  }
  
  /**
     Returns the number of entries in the map.
  **/
  u32int length()
  {
    return nEntries;
  }
      
  
private:
  /**
    A representation of a node
  **/
  class Node
  {
  public:
    Node(K key, T value, class Node *next=NULL) :
      key(key), value(value), next(next)
    {
    }
    
    ~Node()
    {
    }
    
    K key;
    T value;
    class Node *next;
  };
  
  /**
    The hash array
  **/
  Node *array[S];

  /**
     How many entries are in the map.
  **/
  u32int nEntries;
  
  /**
    The predicate to use to check equality of keys
  **/
  EqualityPredicate predicate;
  
  /**
    The function used to generate our hash values.
  **/
  HashFunction hash;
};

#endif
